package dataStructure;

import java.util.ArrayList;

public class Sort {
    private static ArrayList<Integer> list = new ArrayList<>(){{
        add(49);
        add(38);
        add(65);
        add(97);
        add(76);
        add(13);
        add(27);
    }};

    /**
     * 直接插入排序，无哨兵
     * @return
     */
    static ArrayList<Integer> InsertSort(){
        Integer temp;
        int j;
        for (int i = 1; i < list.size() ; i++) {
            if (list.get(i)<list.get(i-1)){
                temp = list.get(i);
                for ( j = i-1; j >=0&&list.get(j)>temp ; --j) {
                    list.set(j+1,list.get(j));
                }
                list.set(j+1,temp);
            }

        }
        return list;
    }

    static ArrayList<Integer> InsertSortByHalf(){
        int j,low,high,mid,temp;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i)<list.get(i-1)){
                temp = list.get(i);
                low = 0;
                high = i-1;
                while (low<=high){
                    mid = (low+high)/2;
                    if (list.get(mid)>temp){
                        high = mid-1;
                    }else {
                        low = mid+1;
                    }
                }
                for (int k = i-1; k >=low; --k) {
                    list.set(k+1,list.get(k));
                }
                list.set(low,temp);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(InsertSortByHalf());
    }
}
